package main

import "math/rand"

type RandomizedSet struct {
	m    map[int]int
	nums []int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		m: make(map[int]int),
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.m[val]; ok {
		return false
	}
	this.nums = append(this.nums, val)
	this.m[val] = len(this.nums) - 1
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	i, ok := this.m[val]
	if !ok {
		return false
	}
	this.m[this.nums[len(this.nums)-1]] = i
	this.nums[i], this.nums[len(this.nums)-1] = this.nums[len(this.nums)-1], this.nums[i]
	this.nums = this.nums[:len(this.nums)-1]
 	delete(this.m, val)
	return true
}

func (this *RandomizedSet) GetRandom() int {
	return this.nums[rand.Intn(len(this.nums))]
}


func main() {
	s := Constructor()
	s.Insert(1)
	s.Insert(2)
	s.Remove(1)
	res := s.GetRandom()
	println(res)

}